1. Field of the Invention
This invention generally relates to real-time, interactive animation of objects, and, more specifically, to real-time, interactive animation of two- and three-dimensional deformable objects.
2. Background
A mass-spring system is a useful way to model a deformable two- or three-dimensional body in an environment in which the body is subject to external forces. According to a technique known as explicit Euler integration, the forces on the mass points of the object at the beginning of a time period xcex94t are used to estimate the velocities and locations of the mass points at the end of the time period xcex94t. The explicit Euler integration step may be used to estimate the locations of the mass points of the object over successive time periods. Deformation of the object resulting from the external forces can be animated by displaying the object as represented by these updated mass points over successive time periods.
A problem with the explicit Euler technique, however, is that, in order to achieve stability, the duration of the time period over which the explicit integration is performed should be inversely proportional to the stiffness of the mass-spring system used to model the object. Since most real-world objects will require relatively stiff springs for modeling purposes, the duration of the time period over which the integration must be performed will be relatively small. The smaller the time period over which the integration is performed, the slower the resulting animation of the object. The result is that, using the explicit Euler integration technique, the majority of real-world objects cannot be animated in real-time. Moreover, all known techniques which have been attempted to overcome this problem yield results which lack realism.
For further background on the subject, the reader is referred to xe2x80x9cInteractive animation of structured deformable objects,xe2x80x9d Mathieu Desbrun et al., Graphics Interface ""99 Proceedings, pp. 1-8, June, 1999, Kingston, Ontario; xe2x80x9cInteractive Animation of Cloth-like Objects for Virtual Reality,xe2x80x9d Mathieu Desbrun et al., published in xe2x80x9cCloth Modeling and Animation,xe2x80x9d A. K Peters, Ltd., Publisher, Donald H. House and David E. Breen, Editors, Kathryn Maier, Associate Editor, Apr. 30, 2000; and xe2x80x9cInteractive Animation of Cloth-like Objects in Virtual Reality,xe2x80x9d Mark Meyer et al., submitted for publication in Journal of Visualization and Computer Graphics. All of these papers or publications are hereby incorporated by reference herein as through set forth in full.
Accordingly, there is a need for a system of and method for animating two- and three-dimensional objects which overcomes one or more disadvantages of the prior art.
There is also a need for a system of and method for animating two- and three-dimensional objects in real-time while maintaining realistic animation quality.
A further need is for a system of and method for animating two- and three-dimensional objects which fulfills any of the foregoing needs, singly or in combination.
In accordance with the purpose of the invention as broadly described herein, there is provided a method for updating the locations and velocities of the mass points of a two- or three-dimensional object to reflect passage of a time period having a duration xcex94t. The object is represented by a mass-spring system comprising a plurality of mass points interconnected with springs. In one embodiment, the method comprises the steps of: performing a modified implicit integration step to determine new locations of the mass points of the object after a time period xcex94t, optionally correcting the new locations of the mass points of the object after the time period xcex94t in order to preserve angular momentum, and optionally further correcting the new locations of the mass points of the object after the time period xcex94t to correct for high stiffness or long time step conditions.
In one embodiment, the method further comprises displaying the object as represented by the corrected locations of the mass points, and successively repeating the foregoing steps over at least one successive time period.
In one configuration, the modified implicit integration step comprises the substeps of calculating the internal force on each mass point of the object at the beginning of the time period xcex94t due to the action of springs; adding an artificial viscosity term to each of these internal forces; filtering out high frequencies from the resultant forces; calculating new velocities for each of the mass points of the object using the filtered forces and any external force applied to the mass points; and calculating new positions for each of the mass points of the object from the updated velocities.
In one implementation, the modified implicit integration step is preceded by a precomputation step in which an nxc3x97n matrix H is precomputed, where n is the number of mass points in the object. The matrix H is defined such that Hij, for ixe2x89xa0j, is equal to kij, where kij is the spring constant for the spring between the ith and jth mass points of the object, and Hij is equal to   -            ∑              j        ≠        i              ⁢          xe2x80x83        ⁢                  k        ij            .      
This latter term is the negative of the sum of the spring constants for all mass points connected to mass point i with a spring.
Once the matrix H has been precomputed, the matrix W is precomputed in accordance with the following expression:   W  =            (                        I          n                -                                            dt              2                        m                    ⁢          H                    )              -      1      
where In is the nxc3x97n identity matrix, dt is the duration time period over which the implicit integration is being performed, m is the mass of a single mass point, and H is the hessian matrix previously discussed.
The precomputation step in this implementation is next followed by a series of steps in which, for each mass point i, the internal force Fi on the mass point due to the action of springs i is first determined, and then an artificial viscosity term is computed and added to this internal force. This series of steps can be represented by the following pseudo-code:
For each mass point i
Fi=0
For each mass point j linked to mass point i with a spring       F    i    =            F      i        +                  k        ij            ⁢              (                              "LeftBracketingBar"                                          x                i                            -                              x                j                                      "RightBracketingBar"                    -                      l            ij            0                          )            ⁢                                    x            i                    -                      x            j                                    "LeftBracketingBar"                                    x              i                        -                          x              j                                "RightBracketingBar"                    xe2x80x83Fi=Fi+kijdt(vjxe2x88x92vi)
In the foregoing, Fi is the force on mass point i due to springs and viscosity, kij is the spring constant for the spring between mass points i and j, xi is the vector representing the current location of mass point i, xj is the vector representing the current location of mass point j, lij0 is the rest length of the spring between mass points i and j, dt is the duration of the time step over which the implied integration step is being performed, vi is the current velocity of mass point i, and vj is the current velocity of mass point j.
This series of steps is then followed in this implementation by a series of steps to filter out high frequencies from the force field determined in the previous series of steps, and to determine updated velocities and locations for each of the object mass points. This series of steps can be represented by the following pseudo-code:
For each mass point i             F      i      filtered        =                  ∑        j            ⁢              xe2x80x83            ⁢                        F          j                ⁢                  W          ij                                v      i              n        +        1              =                  v        i        n            +                        [                                    F              i              filtered                        +                          F              i              ext                                ]                ⁢                  dt          m                    xe2x80x83xinew=xi+vin+1dt
In the foregoing, Fj is the force on mass point j computed in the previous loop of pseudo-code, Wij is the element of matrix W located at the intersection of the ith row and jth column, Fiext is the external force exerted on mass point i, m is the mass of a single mass point, vin is the velocity of mass point i at the inception of the time period of duration dt, xi is the location of mass point i at the inception of the time period of duration dt, vin+1 is the updated velocity of a mass point, and xinew is the updated location of the mass point.
The addition of an artificial viscosity term to the internal forces due to springs, filtering of the resultant forces to remove one or more high frequencies, and use of a constant matrix W to perform this high frequency filtering are all independent aspects of the invention which may be present separately or collectively in various embodiments of the invention.
Once the modified implicit integration step has been performed, the next step comprises optionally correcting the updated locations of the mass points in order to preserve angular momentum. In one implementation, this step is performed first by calculating the center of gravity of the object xG in accordance with the following equation:             x      G        =                  (                              ∑            i                    ⁢                      xe2x80x83                    ⁢                      x            i                          )            n        ,
in which n is the number of mass points in the object. Then, the global torque xcex4T created by the filtered force is computed using the following equation:       δ    ⁢          xe2x80x83        ⁢    T    =            ∑      i        ⁢          xe2x80x83        ⁢                  F        i        filtered            ⊗                        x          i                .            
Next, a corrective displacement for each mass point i, Dicorr, is computed in accordance with the following equation: Dicoor=(xGxe2x88x92xi){circle around (xc3x97)}xcex4T. Finally, the updated location of each mass point, xinew is corrected in accordance with the following equation:       x    i    new    =            x      i      new        +                  D        i        corr            ⁢                                    dt            2                    m                .            
Finally, an optional correction step is performed to accommodate cases involving high stiffness springs or large time periods. In one implementation, this step is performed by iterating through all or substantially all of the pairs of mass points joined by a spring, and checking to see if the spring length lij between mass points i and j exceeds the rest length, lij0, by a predetermined maximum amount such as, for example, 10%. If this condition is present, the two mass points are moved closer together in equal measures until the distance between the two equals the rest length plus the predetermined maximum amount. The only exception to this remedy is if movement of one of the mass points is constrained in some way, such as if it is being held for example. In this case, the unconstrained mass point is moved closer to the constrained mass point until the length between the two is at the predetermined maximum.
In this implementation, this process continues to iterate until one of the following three conditions are present. First, the distance between none of the mass point pairs exceeds the predetermined maximum. Second, the number of iterations equals or exceeds a predetermined maximum number of iterations. Third, a predetermined maximum time limit is equaled or exceeded.
In addition to the foregoing methods, related processor readable media, network accessible servers, and systems in accordance with the subject invention are also provided.